package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._排列组合._基本_排列组合数;

/**
 * https://www.cnblogs.com/1024th/p/10623541.html
 *
 * 分类加法原理：做一件事，有 𝑛 类办法，在第1类办法中有𝑚1种不同的方法，在第2类办法中有𝑚2种不同的方法，…，在第𝑛类办法中有𝑚𝑛种不同的方法，那么完成这件事共有𝑁=𝑚1+𝑚2+…+𝑚𝑛种不同的方法。
 * 分步乘法原理：做一件事，需要分成 𝑛 个步骤，做第1步有𝑚1种不同的方法，做第2步有𝑚2种不同的方法，…，做第𝑛步有𝑚𝑛种不同的方法,那么完成这件事共有𝑁=𝑚1×𝑚2×⋯×𝑚𝑛种不同的方法。
 *
 * 排列数：从 n 个不同元素中，取出 m 个元素组成的 不同的排列数 即为 Anm；
 *                                           当 m=n 时 即为 Ann；
 * 组合数：从 n 个不同元素中，取出 m 个元素的取法，即为 Cnm；
 *
 * Anm = n(n-1)(n-2)...(n-m+1) = Cnm * Amm
 * Ann = n!
 * Cnm = (n(n-1)(n-2)...(n-m+1)) / n!
 * Cnn = 1
 *
 * 基本核心题型总结：
 *      无重复元素
 *          求 Anm : dfs 的结束条件 == k，for 0~n-1，add visited dfs remove visited
 *                  去重条件：visited
 *          求 Cnm : dfs 的结束条件 == k，for index~n-1，add dfs remove
 *
 *      有重复元素
 *          求 Anm : dfs 的结束条件 == k，for 0~n-1，add visited dfs remove visited
 *                  去重条件：visited     i>0 && nums[i]==nums[i-1] && visited[i-1]==false
 *          求 Cnm : dfs 的结束条件 == k，for index~n-1，add remove
 *                  去重条件：i>index && nums[i]==nums[i-1]
 *
 * dfs 可用于解决的问题：排列，组合，子集，子集和，划分子集
 */
public class _000_排列组合常用概念 {
}
